Dilworth 定理

发布于 2020-12-23 | 分类于图论 | 2分钟 | 418字数 | 浏览量：

一.一些定义

若一个集合 $A$ , 满足一种关系 $\le$ ，且满足

那么 $(A,\le)$ 为一个偏序集。

在 $A$ 的一个子集中，如果每两个元素都是可比的，则称这个子集为链。

在 $A$ 的一个子集中，如果每两个元素都是不可比的，则称这个子集为反链。

对于任意有限偏序集，其最大反链中元素的数目等于最小链划分中链的数目。

对于任意有限偏序集，其最长链中元素的数目等于其最小反链划分中反链的数目。

求出一个序列的最长不上升子序列和至少被划分为多少个不上升子序列。

偏序关系 $\le$ : $i < j$ 且 $a_i \ge a_j$

第一问最长链。

第二问求最小链划分，转换为最长反链（ $i < j$ 且 $a_i > a_j$ ），即最长下降子序列。

两问均可以 dp $\mathcal(n \log n)$ 求得。

其余偏序关系同理。

将最长反链转换为最小链覆盖，然后用网络流求解。